import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{4, 7, 6, 8, 35, 9, 1, 26}));
        /*int[] all = new int[20000];
        for (int i = 0; i < 20000; i++) {
            all[i] = i;
        }
        System.out.println(largestRectangleArea(all));*/
    }

    /**
     * 纯计算
     * @param heights
     * @return
     */
    public static int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;
        int max = heights[0];
        int pre, min, area, head;
        for (int i = 1; i < len; i++) {
            if (heights[i] == 0) continue;
            min = heights[i];
            // 计算至少需要往前推的值，如果不满足则继续
            pre = Math.max(max / min, 1);
            if (pre > i) continue;
            for (int j = 0; j < pre; j++) {
                // 找到i和pre直接的最小值
                min = Math.min(heights[i - j], min);
            }
            head = max / len - 1;
            for (int j = i - pre; j >= 0; j--) {
                // 从当前位置i往前算
                min = Math.min(min, heights[j]);
                area = Math.max(heights[i], min * (i - j + 1));
                if (area > max) {
                    max = area;
                }
                // 当最小值已经小于了可能性的值，就没必要算了
                if (min < head) break;
            }
        }
        return max;
    }

    /**
     * 单调栈
     * 用单调栈求某个节点高度允许的的左边最小和右边最小
     * 乘上高度就是答案
     * @param heights
     * @return
     */
    public static int largestRectangleArea1(int[] heights) {
        int n = heights.length;
        // left记录的是上一个当前值小的位置是什么
        int[] left = new int[n];
        // right记录的是上一个当前值大的位置是什么
        int[] right = new int[n];

        Stack<Integer> monoStack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
                monoStack.pop();
            }
            left[i] = (monoStack.isEmpty() ? -1 : monoStack.peek());
            monoStack.push(i);
        }

        monoStack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
                monoStack.pop();
            }
            right[i] = (monoStack.isEmpty() ? n : monoStack.peek());
            monoStack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            // 根据两个单调栈算出最大值
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

    public static int largestRectangleArea(int[] heights) {
        int res=heights.length;
        for (int i = 0; i < heights.length; i++) {

        }
        return res;
    }

}